package org.alg.graph;

/**
 * Created with IntelliJ IDEA.
 * User: Administrator
 * Date: 15-5-3
 * Time: 下午11:15
 * To change this template use File | Settings | File Templates.
 */
public class Cycle {

    private boolean[] marked;
    private boolean hasCycle;

    public Cycle(Graph graph){
        marked=new boolean[graph.V()];
        for(int s=0;s<graph.V();s++){
            if(!marked[s])
                dfs(graph,s,s);
        }
    }

    public void dfs(Graph graph,int v,int u){
        marked[v]=true;
        for(int w:graph.adj(v)){
            if(!marked[w]){
                dfs(graph, w, v);
            }else if(w!=u){
                hasCycle=true;
            }
        }
    }

    public boolean isHasCycle(){return hasCycle;}

}
